package com.data_structure_algorithm.algorithm;

import java.util.Arrays;

/**
 * @Authror PABLO
 * @Date 2022/4/5 11:52
 * @Desc 非递归实现二分查找
 */
public class BinarySearch {

    public static void main(String[] args) {

        int[] arr = {8, 9, 6, 3, 1, 4, 5, 4, 5, 2, 12, 63};


        sort(arr, 0, arr.length - 1, new int[arr.length]);


        System.out.println(Arrays.toString(arr));

    }

    private static void sort(int[] arr, int left, int right, int[] temp) {

        if (left < right) {
            int mid = (left + right) / 2;

            //左拆分
            sort(arr, left, mid  , temp);

            sort(arr, mid + 1, right, temp);

            merge(arr,left,mid,right,temp);
        }


    }

    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        //确定两端左侧数据

        int i = left;

        int j = mid + 1;

        //  临时数组下标
        int tempIndex = 0;

        //左右比较
        while (i <= mid  && j <= right) {

            //比较两侧大小
            if (arr[i] <= arr[j]) {
                temp[tempIndex++] = arr[i++];
            }

            if (arr[i] >= arr[j]) {
                temp[tempIndex++] = arr[j++];
            }
        }

        //判断
        while (i <= mid ) {
            temp[tempIndex++] = arr[i++];
        }
        while (j <= right) {
            temp[tempIndex++] = arr[j++];
        }


        //临时数组数据转移到原数组

        tempIndex = 0;

        int srcLeft = left;

        while (srcLeft <= right) {
            arr[srcLeft++] = temp[tempIndex++];
        }
    }

}
